#include <iostream>
#include <vector>
#include <unistd.h>
#include <cmath>

//class Solution {
//    int _dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
//    int _dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
//    int _k = 0;
//    int _n = 0;
//    int _cnt = 0;
//
//    void dfs(int x, int y)
//    {
//	// std::cout << "_k: " << _k << std::endl;
//	if (_k == 0) {
//	 std::cout << "x: " << x << " y: " << y << std::endl;
//      }
////	 usleep(700);
//        if (_k == 0) {
//            ++_cnt;
//            return;
//        }
//        for (int i = 0; i < 8; ++i)
//        {
//            int nextX = x + _dx[i], nextY = y + _dy[i];
//            if (nextX >= 0 && nextX < _n && nextY >= 0 && nextY < _n) {
//                --_k;
//                dfs(nextX, nextY);
//                ++_k;
//            }
//        }
//    }
//
//public:
//    double knightProbability(int n, int k, int row, int column)
//    {
//        _k = k;
//        _n = n;
//        dfs(row, column);
//        return _cnt / pow(8, k);
//    }
//};
#include <cmath>

class Solution {
    std::vector<int> dx = { -2, -1, 1, 2, 2, 1, -1, -2 };
    std::vector<int> dy = { 1, 2, 2, 1, -1, -2, -2, -1 };

    double dfs(int x, int y, int k, int n) {
        if (k == 0) return 1.0; // Base case: if no moves left, return probability 1
        if (x < 0 || x >= n || y < 0 || y >= n) return 0.0; // If out of bounds, return probability 0
        double prob = 0.0;
        for (int i = 0; i < 8; ++i) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            prob += dfs(nextX, nextY, k - 1, n) / 8.0; // Accumulate probability of all valid moves
        }
        return prob;
    }

public:
    double knightProbability(int n, int k, int row, int column) {
        return dfs(row, column, k, n);
    }
};

int main()
{
   std::cout << Solution().knightProbability(8, 30, 6, 4) << std::endl;
   return 0;
}
